#include <bits/stdc++.h>
// 2025/02/04
// tag: 
// Author: Zhang Muen
using namespace std;

using int64 = int64_t;
int n, m, profit[11][16], dp[11][16], RightPath[11][16][11];

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> profit[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = j; k >= 0; k--)
                if (dp[i - 1][j - k] + profit[i][k] > dp[i][j]){
                    dp[i][j] = dp[i - 1][j - k] + profit[i][k];
                    for (int l = 1; l < i; l++)
                        RightPath[i][j][l] = RightPath[i - 1][j - k][l];
                    RightPath[i][j][i] = k;
                }
    cout << dp[n][m] << endl;
    for (int i = 1; i <= n; i++)
        cout << i << " " << RightPath[n][m][i] << endl;
    
    return 0;
}